COMMENT ⊗   VALID 00001 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 ENDMK
C⊗;
∂17-Oct-79  1329	PJH  
hi, thanks for your flattering msge. sorry for the long delay in
replying., but ive been down with flu for sabout 2 weeks.
this is really just a placeholder for as longwr msge answering
yours which will arrive in a few days. best wishes., pat hayes.

∂17-Oct-79  1331	PJH  	adresses 
ps. both kowalski and keith clark are now at imperial college.
adress is: Dept. of computing and Control
Huxley Building
Queensgate
London  SW

there is a proper zipcode but i dont think its
presence makes more than a few hoyurs differencse.
pps: insert   "imperial College" between second and third lines of
the above. I too am working remotely at 300 baud, isnt it 
a pig?

∂19-Oct-79  1133	PJH  	theory courses
its rather difficult to make suggestions about courses without
knowing about the other courses, the background of the students,
etc. however, here aree my very tentative suggestions.
(1) there surely has to be a course on the basic ideas of computability
theory. this could coverthe idea of computability and uncomputability,
the various models of general comutability and how one shows them
equivalent(turing machines, recursive function definitions,perhaps
other kinds of automaton). I think its instructive to see how one
of these is encoded in the others, even aside from the
theoreetical significance.Also its instructive what a difference
memory makes: after all, a turing machine is just a finitestate
machine with an infinite memory.
this course could also serve a useful role in introducing various
formalisms and notations, eg lambdaclaculus,predicate calculus.
(2)proving properties of programs/algorithms.
termination and correctness(moral:correctness is actually
pretty trivial to demonstrate: its termination thats hard, usually)
(thats partial correctness, of course)This course could go several ways
:it could emphasise the various formalisms that have been invented
(manna, hoare, floyd,pratt, algorithmic logic) or it could be organised
more around the various forms and guises in which istructural induction
appears, for example.It could be given a sort of practical emphasis,
along the lines of Dijkstas writings, ie the proof of the program
is really implicit in the process of understanding the program,
or even inventing it: opr it can be given a much more theoretical emphasis,
relating the variouys inductions to deep principles of computability.
Let me suggest that you get hold of a copy of the forthcoming book
(called, misleadingly,"a theorem prover", by Boyer and Moore
of SRI, which has a nice account of a powerful induction
principle.) another closely related area that could be covered by the
same course is the recent work on synthesising and "improving" programs
by manipulating collections of equations. This is the stuff that Burstall,
darlington, clark have been doing (darlington is also at Imperial College)
A general moral of all this work , it seems to me, is that in order
to  manipulate and describe programs, they have to be regarded
as collections of assertions(maybe equations). Even eg the flold technique
can be looked at in this way, and one can almost regard manna as translating
floxcharts into predicate calculus.
(3) semantics of programming languages, a la scott and strachey. For an excellent
if rather heavy text, see recent book by Joe Stoy. This stuff is 
(a) mathematically beautiful(if done right)(b) usuful, in that it provides
a good way to contrast and compare programming languages (c) has deep
connections with foundational aspects in (1), and finally complements (2) rather
well.
(4) not sure. Perhaps a course on the complexity of algorithms(eg see nice
textbook by aho, hopcroft and ullman). This eemas to engage with a completely
different view of algorithms that that which gives life to the area covered in
(2): with the underlying machine rather than the logical structure of the 
algorithm(?)

But anyway, look: I am no expert in the theory of computer science.Ask
an expert.
If you would like to talk some about this stuff, lets get together
for lunch some time
best wishes
pat hayes